package offer.diff;

/**
 * @author DengYuan2
 * @create 2021-03-06 11:39
 */
public class n_12 {
    public static void main(String[] args) {
        n_12 n = new n_12();
        String s1 = "ABCESFCSADEE";
        String s2 = "SEE";
//        String s2="ABCCED";
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        boolean res = n.hasPath(c1, 3, 4, c2);
        System.out.println(res);
    }

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        int[][] isVisited = new int[rows][cols];
        char[][] path = new char[rows][cols];
        int idx = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                path[i][j] = matrix[idx++];
            }
        }

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (helper(path,i,j,str,0,isVisited)){
                    return true;
                }
            }
        }
        return false;
    }


    public boolean helper(char[][] path, int r, int c, char[] str, int idx, int[][] isVisited) {
        if (idx == str.length) {
            return true;
        }
        if (r < 0 || r >= path.length || c < 0 || c >= path[0].length || str[idx] != path[r][c] || isVisited[r][c] == 1) {
            return false;
        }
        isVisited[r][c] = 1;
        if (
        //右
        helper(path, r, c + 1, str, idx+1, isVisited)
        //左
        || helper(path, r, c - 1, str, idx+1, isVisited)
        //下
        || helper(path, r + 1, c, str, idx+1, isVisited)
        //上
        || helper(path, r - 1, c, str, idx+1, isVisited)
        ){
            return true;
        }
        isVisited[r][c] = 0;
        return false;
    }



}
